import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/26 10:01
 * @description 二分查找
 */
public class Solution {
    public static void main(String[] args) {

    }
    public int nthUglyNumber(int n, int a, int b, int c) {
        // 左边蓝色区域，区间[0,mid]中 丑数个数 < n，右边红色区域，区间 [0, mid]中 丑数 >= n, 返回右指针
        long ab = lcm(a, b), ac = lcm(a, c), bc = lcm(b, c), abc = lcm(ab, c);
        // 二分边界
        long l = Math.min(a, Math.min(b ,c)) - 1, r = (long) (2e9 + 1);
        while (l + 1 != r) {
            long mid = (l + r) / 2;
            // 利用容斥原理，计算[l, mid]中的丑数个数
            long cnt = mid / a + mid / b + mid / c - mid / ab - mid / ac - mid / bc + mid / abc;
            if (cnt < n) {
                l = mid;
            }else {
                r = mid;
            }
        }
        return (int) r;
    }

    public long gcd (long a, long b) {
        return b != 0 ? gcd(b, a % b) : a;
    }

    public long lcm(long a, long b) {
        return a * b / gcd(a, b);
    }
}
